package zuoshen_video2.dynamic;

import java.util.Arrays;

import org.junit.Test;

public class MinCoins {
    
    //使用一维数组存储硬币，每个位置代表硬币的币值，试问拼凑出目标值的最少硬币数量

    public int maxCoins1(int[] nums, int t) {
        return dfs1(0, 0, 0, nums, t);
    }

    public int dfs1(int cur, int idx, int num,int[] nums, int t) {
        if (cur >= t) return cur == t ? num : Integer.MAX_VALUE;
        //注意点：为了求最小的硬币数，有必要让不能求得为最大。
        if (idx == nums.length) return cur == t ? num : Integer.MAX_VALUE;
        int get = dfs1(cur + nums[idx], idx + 1, num + 1, nums, t);
        int cast = dfs1(cur, idx + 1, num,nums, t);
        return Math.min(get, cast);
    }

    @Test
    public void test1() {
        int[] nums = {2, 7, 3, 5, 3, 3, 1};
        System.out.println(maxCoins1(nums, 10));
    }

    //换减小来
    public int maxCoins2(int[] nums, int t) {
        p = new int[t + 1][nums.length + 1][nums.length];
        return dfs2(t, 0, 0, nums);
    }

    int[][][] p;
    public int dfs2(int cur, int idx, int num, int[] nums) {
        if (cur < 0) return Integer.MAX_VALUE;
        if (p[cur][idx][num] != 0) return p[cur][idx][num];
        if (cur == 0) {
            p[cur][idx][num] = num;
            return num;
        }
        //注意点：为了求最小的硬币数，有必要让不能求得为最大。
        if (idx == nums.length) {
            p[cur][idx][num] = cur == 0 ? num : Integer.MAX_VALUE;
            return p[cur][idx][num];
        }
        int get = dfs2(cur - nums[idx], idx + 1, num + 1, nums);
        int cast = dfs2(cur, idx + 1, num, nums);
        p[cur][idx][num] = Math.min(get, cast);
        return p[cur][idx][num];
    }

    @Test
    public void test2() {
        int[] nums = {2, 7, 3, 5, 3, 3, 1};
        int res = maxCoins2(nums, 10);
        System.out.println(Arrays.deepToString(p));
        System.out.println(res);
    }

     public int maxCoins3(int[] nums, int t) {
         int len = nums.length;
         //第一维：残余的目标值； 第二维：当前遍历到的位置 第三维：当前的硬币数量
        int[][][] f = new int[t + 1][nums.length + 1][nums.length + 1];

        for (int i = 0; i <= t; i++) { //残余
            for (int j = len; j >= 0; j--) { //idx
                for (int k = len; k >= 0; k--) { //num
                    if (i == 0) f[i][j][k] = k;
                    else if (j == len || k == len) f[i][j][k] = Integer.MAX_VALUE;
                    else if (i >= nums[j]) {
                        f[i][j][k] = Math.min(f[i - nums[j]][j + 1][k + 1], f[i][j + 1][k]);
                    } else f[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }
        System.out.println(Arrays.deepToString(f));
        return f[t][0][0];
    }

    @Test
    public void test3() {
        int[] nums = {2, 7, 3, 5, 3, 3, 1};
        int res = maxCoins3(nums, 10);
        System.out.println(res);
    }


    //4. 利用-1表示无效解降低维度
        public int maxCoins4(int[] nums, int t) {
            p2 = new int[t + 1][nums.length + 1];
            for (int i = 0; i < t + 1; i++) {
                Arrays.fill(p2[i], -2);
            }
            return dfs4(t, 0, nums);
        }
    
        int[][] p2;
        public int dfs4(int cur, int idx, int[] nums) {
            if (cur < 0) return -1;
            if (p2[cur][idx] >= -1) {
                return p2[cur][idx];
            }
            if (cur == 0) {
                p2[cur][idx] = 0;
                return p2[cur][idx];
            }
            if (idx == nums.length) {
                p2[cur][idx] = -1;
                return p2[cur][idx];
            }
            
            int use = dfs4(cur - nums[idx], idx + 1, nums);
            int not = dfs4(cur, idx + 1, nums);
            if (use == -1 && not == -1) p2[cur][idx] = -1;
            else {
                if (use == -1) p2[cur][idx] = not;
                else if (not == -1) p2[cur][idx] = use + 1;
                else p2[cur][idx] = Math.min(not, use + 1);
            }
            return p2[cur][idx];
        }

        public int dfs5(int cur, int idx, int[] nums) {
            if (cur == 0) return 0;
            if (cur < 0 || idx == nums.length) return -1;
            int use = dfs5(cur - nums[idx], idx + 1, nums);
            int not = dfs5(cur, idx + 1, nums);
            if (use == -1 && not == -1) return -1;
            else {
                if (use == -1) return not;
                else if (not == -1) return use + 1;
                else return Math.min(not, use + 1);
            }
        }
    
        @Test
        public void test4() {
            int[] nums = {2, 7, 3, 5, 3, 3, 1};
            int res = maxCoins4(nums, 10);
            
            System.out.println(Arrays.deepToString(p2));
            System.out.println(res);
        }
    

}
